Raytracing is a field of computer graphics that can produce superior, photorealistic digital images. Raytracing or ray-casting is a three-dimensional (3-D) rendering technique that determines the location of an object in 3-D and calculates shadows, reflections, and hidden surfaces based on lighting conditions and locations, as well as material characteristics. The visibility of surfaces is determined by tracing rays of light from the viewer's vantage to objects in a scene.
Raytracing differs from z-buffer oriented methods by being ray centric, as opposed to primitive centric. Instead of drawing primitives to a screen, rays are cast from a virtual eye, or center of projection, through screen pixels (i.e., a view plane) to find intersecting primitives for those pixels. Each pixel has a color set to that of the primitive at the closest point of intersection. While raytracing has existed for quite some time, only recently has research started to make raytracing algorithms run in realtime. Current applications for raytracing include movie and advertising business for precalculated visualisations.
Interactive and realtime raytracing are closely related areas, but are not quite the same. “Interactive” refers to the ability to compute scenes at realtime speeds, without prior knowledge of future frames (e.g., a user may be able to control scene content directly). “Realtime” refers to the ability to compute scenes at speeds sufficiently high to convey the perception of motion to the human eye and allowing an algorithm with knowledge of future frames (more of a prescripted movie approach to animation).
A major limitation on the application of raytracing is the significant computational requirements incurred to render images. A number of proposals have been made to increase the efficiency of raytracing to expand its use in computer graphics. A number of algorithms and architectures for image generation are described by Szirmay-Kalos, László, Theory of Three Dimensional Computer Graphics, Chp. 2, pp. 25–52. In particular, Szirmay-Kalos describes a Digital Differential Analyzer (DDA) line generator used to generate pixel data by applying an incremental concept to scan-line conversion. For a linear function, a line can be drawn using the DDA that eliminates multiplication, non-integer addition, and round operations. The slope of a line is calculated once and is then used to incrementally determine or generate the line.
Fujimoto, A., Tanaka, T., and Iwata, K., “ARTS: Accelerated Ray-Tracing System”, IEEE CG&A, April 1986, pp. 16–26 describe a three-dimensional digital differential analyzer (3DDDA) that seeks to address issues of speed and aliasing in ray-tracing. The 3DDDA is a 3D line generator for traversing a data structure describing a 3-D environment to identify the intersections between rays and objects in the image to be generated. The 3DDDA identifies cells pierced by a ray or straight line and generates the coordinates of the cells. One implementation of a 3DDDA is to use two DDAs synchronized to work in mutually perpendicular planes that intersect along a driving axis DA (i.e., a coordinate axis). In each plane, the respective DDA follows the projection of the 3-D line onto that plane. The coordinate corresponding to the driving axis DA of each DDA is unconditionally incremented by one unit, where the DA is determined by the slope of the line. A control term (or error term) for each DDA measured perpendicular to the DA is updated; this is done by subtracting from the control term the slope value and determining if it satisfies a stipulated condition. Both control terms are measured against the same DDA. If the test fails, a unit increment or decrement of the coordinate perpendicular to the DA is performed for the DDA. The control term is corrected by adding the value corresponding to one pixel whenever underflow occurs.
Setting up the rays cast from a viewpoint into a 3D scene representation is implemented conventionally as depicted in FIG. 1. To raytrace a three-dimensional (3D) image, for each pixel, one or more rays are typically cast from the viewpoint through the screen into the 3D world. Rays are shot through pixels in the viewport. As shown in FIG. 1, such a viewport 100 is considered a perspective correct viewport if the screen surface is planar, where:    P=Viewpoint in 3D world, or base vector,    T=T is the vector from P to the top left corner of the screen,    H=Vector representing 2D horizontal scanline in 3D world, and    V=Vector representing 2D vertical screen in 3D world.H is the vector from the top left corner of the screen to the top right corner of the screen, and V is the vector from the top left corner of the screen to the bottom left corner of the screen.
From T, H, V and P, a planar region is formed that maps to the screenspace coordinates such that a ray cast from P to this plane corresponds to a pixel on the screen provided the ray intersects the planar region mentioned.
To form the rays for all pixels on the screen, pseudo-code such as that shown in Table 1 may be used.
TABLE 1Let vector R be TLet vector Hstep be H / (horiz-res)Let vector Vstep be V / (vert-res)for all y, 0 to vert-res Let vector S be R for all x, 0 to horiz-res  Cast-ray S  S = S + Hstep end for R = R + Vstepend for
In Table 1, the vector R is initialised to the vector T. The term “horiz-res” in Table 1 represents the horizontal sampling resolution on the screen, and the term “vert-res” represents the vertical sampling resolution on the screen. Hstep and Vstep are the horizontal and vertical incremental steps, respectively. The pseudocode operates on a horizontal scanline beginning with the topmost one, and then processes each horizontal scanline moving down by one vertical step. This is done iteratively. For each scanline, the vector S is initialised. Raycasting (“Cast-ray”) is performed for S, before S is incremented by Hstep, which steps are iteratively carried out until the horizontal resolution (horiz-res) is reached. “Cast-ray” casts the ray S from P into the 3D geometry to perform raytracing and determine the color of the pixel (x, y) of the screen. The vector R is then incremented by Vstep. This processing continues iteratively until the vertical resolution is reached (vert-res).
The above pseudo code is a generalization. Additional considerations such as anti-aliasing, object and viewpoint transformations, distributed raytracing (the introduction of time-based jittered variations in aforementioned transformations) or other techniques not specifically mentioned may influence the actual implementation.
The “Cast-ray” operation takes the ray, and in anything other than a non-representative, simplistic, un-optimized raytracer, prepares the ray for traversal of a spatial subdivision structure. The spatial subdivision structure may include a binary space-partitioning tree (bsp-tree), an octree, a grid, or a nested grid. Other spatial subdivision techniques may be practiced. For the “Cast-ray” operation, the initialization of variables required for traversing the spatial subdivision structure is computationally intensive. The initialization involves computationally expensive operations including multiplications and in particular divisions for each ray. Even for a low-resolution image, this cost is significant. For example, a low sampling resolution of 1024*768 results in 786,432 rays being cast, each ray requiring 3 divisions for initialization. This results in 2,359,296 divisions per frame. Clearly, improvement is required to reduce computational cost in a software implementation, and both gate-count and complexity in a hardware implementation.
Thus, a need clearly exists for an improved method of ray-tracing using a multi-dimensional DDA that reduces computational complexity and time for cast rays.